class Record {
	int mMode;	// 文件权限
	String mType;   // 节点类型，取值为“blob” 和“tree”
	String mId;   //标识该文件的sha-a字符串
	String mName;  //文件或文件夹名
}

class Tree extends ArrayList<Record> {
	Tree(String id) {
		//根据treeId构造出Tree对象，使用libgit可以得到这些信息，此处省略具体逻辑。
	}	
}

class CatcheRecord {
	// 根据record 和CommitId构造
	CatcheRecord (Record record, String commitId) {
		mMode = record.mMode;
		mType = record.mType;
		mId = record.mId;
		mName = record.mName;
		mCommitId = commitId;
		if (mType.equals("tree")) {
			mCatcheTreeId = CatcheTreeHelper.generateCatcheTreeId(mId, commitId);
		}
	}
	int mMode;	// 文件权限
	String mType;   // 节点类型，取值为“blob” 和“tree”
	String mId;   //标识该文件的sha-a字符串
	String mName;  //文件或文件夹名
	String mCommitId;   // 指向提交此记录的Commit对象
	String mCatcheTreeId;   // 如果mType为“tree”,此值有效，表示mId所指向的tree对象对应的CatcheTree的Id
}

class CatcheTree extends ArrayList<CatcheRecord> {

	CatcheTree() {
	}
	
	CatcheTree(String id) {
		//id 也是文件名，可以直接读取对应的文件，构造出该对象，此处神略具体逻辑。
	}	
	
	boolean save (String id) {
		// 把当前对象保存在以id 为文件名的文件中，此处神略具体逻辑。
	}
	
}

class CatcheTreeHelper {
	//根据treeId 和commitId 生成对应的catcheTreeId
	static String generateCatcheTreeId (String treeId, String commitId) {
		int count = 0;      // count 用于解决冲突
		String resultId = null;
		do {
			resultId = sha_1(id, commitId, count++);
			if (count > MAX_TRY) {
				throw Exception ("Not Find");
			}			
		} while (exist(resultId));
		createFile(resultId);  //把对应的文件创建出来，备用
		return resultId;
	}
	
	//情况1，首次提交
	static void generateCatcheTree(String treeId, String commitId, String catcheTreeId) {
		Tree tree = new Tree(treeId);
		CatcheTree catcheTree= new CatcheTree();
		for (Record record : Tree) {
			CatcheRecord catcheRecord = new CatcheRecord(record, commitId);
			
			if (record.mType.equals("tree")) {
				//递归，创建当前目录下各个子目录的CatcheTree对象。
				generateCatcheTree(record.mId, commitId, catcheRecord.mCatcheTreeId)
			}
			catcheTree.add(catcheRecord);
		}
		
		catcheTree.save(catcheTreeId);	
	}
	
	//情况2， 多次提交，无分支
	static void generateCatcheTree(String treeId, String commitId, String catcheTreeId, String parentTreeId) {
		Tree tree = new Tree(treeId);
		CatcheTree catcheTree= new CatcheTree();
		if (parentTreeId == null) {
			//tree 中的文件是第一次提交，属于情况1
			return generateCatcheTree(treeId, commitId, catcheTreeId)
		}
		
		CatcheTree parentTree = new CatcheTree(parentTreeId);
		
		// id 映射到CatcheRecode 对象。
		HashMap<String, CatcheRecord> idToCatcheRecordMap= new HashMap<String, CatcheRecord>();
		for (CatcheRecord parentRecord : parentTree) {
			idToCatcheRecordMap.put(parentRecord.mId, parentRecord);
		}
		
		// 文件名 映射到TreeId。
		HashMap<String, String> nameToCatcheRecordMap= new HashMap<String, String>();
		for (CatcheRecord parentRecord : parentTree) {
			if (parentRecord.mType.equals("tree")) {
				nameToCatcheRecordMap.put(parentRecord.mName, parentRecord.mCatcheTreeId);
			}
		}
		
		for (Record record : Tree) {
			//表示此项纪录所代表的文件不是这次新提交的，而是以前提交过得，所以旧的提交记录仍然有效
			if (idToCatcheRecordMap.get(record.mId) != null) {
				catcheTree.add(idToCatcheRecordMap.get(record.mId)); //直接使用旧记录
			} else {
				//否则创建新纪录
				CatcheRecord catcheRecord = new CatcheRecord(record, commitId);
				if (record.mType.equals("tree")) {
					generateCatcheTree(treeId, commitId, catcheTreeId, nameToCatcheRecordMap.get(record.mName));
				}
			}
		}
		
		catcheTree.save(catcheTreeId);	
	}
	
	//情况3，本次提交来自几个分支的合并。最后一个参数与情况2不同
	static void generateCatcheTree(String treeId, String commitId, String catcheTreeId, ArrayList<String> parentTreeIdArray) {
		Tree tree = new Tree(treeId);
		CatcheTree catcheTree= new CatcheTree();
		if (parentTreeIdArray == null) {
			//tree 中的文件是第一次提交，属于情况1
			return generateCatcheTree(treeId, commitId, catcheTreeId)
		}
		
		// id 映射到CatcheRecode 对象。
		HashMap<String, CatcheRecord> idToCatcheRecordMap= new HashMap<String, CatcheRecord>();
		
		// 文件名 映射到TreeIdArray。
		HashMap<String, ArrayList<String>> nameToArrayCatcheRecordMap= new HashMap<String, ArrayList<String>>();
		
		for (String parentTreeId : parentTreeIdArray) {
			CatcheTree parentTree = new CatcheTree(parentTreeId);
			
			for (CatcheRecord parentRecord : parentTree) {
				CatcheRecord oldRecord = idToCatcheRecordMap.get(parentRecord.mId);
				
				//commitTime() 函数用于计算记录的提交时间，暂未实现。
				//如果有多个分支同时提交了同一个文件，那么合并时，使用更新的提交记录
				if (oldRecord== null || commitTime(parentRecord) > commitTime(oldRecord)) {
					idToCatcheRecordMap.put(parentRecord.mId, parentRecord);
				}
			}
			
			for (CatcheRecord parentRecord : parentTree) {
				if (parentRecord.mType.equals("tree")) {
					ArrayList<String> array = nameToArrayCatcheRecordMap.get(parentRecord.mName);
					if (array == null) {
						array = new ArrayList<String>();
						nameToArrayCatcheRecordMap.put(parentRecord.mName, array);
					}
					array.add(parentRecord.mRecordTreeId);	
				}
			}
		}
		

		
		for (Record record : Tree) {
			//表示此项纪录所代表的文件不是这次新提交的，而是以前提交过得，所以旧的提交记录仍然有效
			if (idToCatcheRecordMap.get(record.mId) != null) {
				catcheTree.add(idToCatcheRecordMap.get(record.mId)); //直接使用旧记录
			} else {
				//否则创建新纪录
				CatcheRecord catcheRecord = new CatcheRecord(record, commitId);
				if (record.mType.equals("tree")) {
					generateCatcheTree(treeId, commitId, catcheTreeId, nameToCatcheRecordMap.get(record.mName));
				}
			}
		}
		
		catcheTree.save(catcheTreeId);		
	}
	
	
	void createCatche(String commitId) {
		if (String catcheTreeId = getFromMap(getTree(commitId))) {
			return ; // 如果缓存已经存在，直接返回
		}
		String[] arrayParentCommitId = getParentCommit(commitId);
		//首次提交情况1
		if (arrayParentCommit == null) {
			String treeId = getTree(commitId); // 解析出Commit对象中的tree对象
			String catcheTreeId = generateCatcheTreeId(treeId, commitId);
			// 建立treeId到catcheTreeId的映射关系，以便通过treeId得到catcheTreeId
			putIntoMap(treeId, catcheTreeId);
			generateCatcheTree(treeId, commitId, catcheTreeId);
		} else {
			ArrayList<String> arrayParentCatcheTreeId = new ArrayList<String>();
			for (String parentCommitId : arrayParentCommitId) {
				//递归，为前面的提交创建缓存。
				createCatche (parentCommitId);
				String treeId = getTree(parentCommitId);
				String catcheTreeId = getFromMap(treeId);  //根据已建好的映射关系得到catcheTreeId；
				arrayParentCatcheTreeId.add(catcheTreeId);
			}
			//此时满足情况3
			generateCatcheTree(treeId, commitId, catcheTreeId，arrayParentCatcheTreeId);
		}
		
		// 建立treeId到catcheTreeId的映射关系，以便通过treeId得到catcheTreeId
		putIntoMap(treeId, catcheTreeId);
	}
	

}






